package demo.practice.dp;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class P416 {

    public static void main(String[] args) {
        P416 p416 = new P416();
        p416.canPartition(new int[]{3, 3, 3, 4, 5});
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {//基数
            return false;
        }
        int target = sum / 2;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(target);

        Set<Integer> visited = new HashSet<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                Integer poll = queue.poll();
                for (int i = 0; i < nums.length; i++) {
                    if (!visited.contains(i)) {
                        int num = nums[i];
                        if (poll != null ) {
                            if(num == poll) {
                                return true;
                            }
                            queue.add(poll - num);
                            visited.add(i);
                        }
                    }
                }
                size--;
            }
        }
        return false;
    }

    //boolean dp[][] = new boolean[nums.length][target + 1];
    // dp[i][j] 代表  有nums[i]参与的情况下是否能凑出和为j的情况
    // 初始态 dp[0][0]= true 且 dp[i][i]=true
    // 转移方程式 dp[i][j]= ( dp[i-k][j-nums[k]]  )
    //dp[0][0] = true;

        /*for (int j = 1; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {


            }
        }*/
}
